package main.贪心;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/8/8 17:16
 * @description 「同一字母最多出现在一个片段中」意味着，一个片段若要包含字母 a，那么所有的字母 a 都必须在这个片段中。
 * 看了灵神的思路，本质就是一个合并区间
 * 边界条件：如果发现end=i，说明当前区间合并完毕
 *
 * 1. 用一个数组来存储每个字母所处字符串的最大下标
 *  last[charArray[i] - 'a'] = i; 这个思路转变的很神奇
 * 2.
 *             //更新当前区间右端点的最大值
 *             end = Math.max(end, last[s.charAt(i) - 'a']);
 * 3. 当end==i的时候，说明找到了要的区间，加入结果中
 */
public class T763划分字母区间 {
    public static void main(String[] args) {
        String s = "ababcbacadefegdehijhklij";
    }

    public List<Integer> partitionLabels(String s) {
        //先用一个数组来存储字符串中的最后一个字符所处的下标
        //因为是26个字母，所以数组的长度是26
        int[] last = new int[26];
        char[] charArray = s.toCharArray();
        //遍历字符数组
        for (int i = 0; i < charArray.length; i++) {
            last[charArray[i] - 'a'] = i;
        }
        //存储结果
        List<Integer> result = new ArrayList<>();
        //定义区间的左右端点
        int start = 0;
        int end = 0;
        //合并区间
        for (int i = 0; i < charArray.length; i++) {
            //更新当前区间右端点的最大值
            end = Math.max(end, last[s.charAt(i) - 'a']);
            //如果end的结果和i相同，就说明当前区间合并完毕
            if (end == i) {
                result.add(end - start + 1);
                //更新start的值
                start = end + 1;
            }
        }
        return result;
    }


//    作者：灵茶山艾府
//    链接：https://leetcode.cn/problems/partition-labels/solutions/2806706/ben-zhi-shi-he-bing-qu-jian-jian-ji-xie-ygsn8/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
